
// 140. 单词拆分II
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        // 依旧是采用动态规划的方式 , 以i位置为结尾能组成句子的所有字符串
        int n = s.size();
        unordered_set<string> st;
        for(auto& str : wordDict) st.insert(str);
        vector<vector<string>> dp(n + 1);
        dp[0] = {""};
        s = " " + s;
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= i ; j++)
            {
                string subs = s.substr(j , i - j + 1);
                if(dp[j-1].size() && st.count(subs))
                {
                    for(auto & str : dp[j-1])
                    {
                        if(j == 1) dp[i].push_back(subs);
                        else dp[i].push_back(str + " " + subs);
                    }
                }
            }
        }
        return dp[n];
    }
};